import java.util.*;

/**
 * 676. 实现一个魔法字典
 * https://leetcode-cn.com/problems/implement-magic-dictionary/
 */
public class Solutions_676 {
    public static void main(String[] args) {
        MagicDictionary magicDictionary = new MagicDictionary();
        String[] dictionary = {"hello", "leetcode", "hallo"};
        magicDictionary.buildDict(dictionary);
        boolean res1 = magicDictionary.search("hello");  // output: true
        System.out.println(res1);
        boolean res2 = magicDictionary.search("hhllo");  // output: true
        System.out.println(res2);
        boolean res3 = magicDictionary.search("hell");  // output: false
        System.out.println(res3);
        boolean res4 = magicDictionary.search("leetcoded");  // output: false
        System.out.println(res4);
        boolean res5 = magicDictionary.search("hallo");  // output: true
        System.out.println(res5);
    }
}

/**
 * 解法二：前缀树 + 深度优先搜索（ms）
 */
class Trie_767 {
    Map<Character, Trie_767> childs = new HashMap<>();
    boolean isWord;
}

class MagicDictionary {
    Trie_767 root = null;

    public MagicDictionary() {
        root = new Trie_767();
    }

    public void buildDict(String[] dictionary) {
        buildTrie(dictionary);
    }

    public boolean search(String searchWord) {
        char[] arr = searchWord.toCharArray();
        return dfs(arr, root, 0, 1);
    }

    /**
     * 深度优先搜索，查找 arr 数组，是否存在于字典树中
     * count：不同字符的数量
     */
    public boolean dfs(char[] arr, Trie_767 node, int index, int count) {
        if (node == null || count < 0) {
            // 结束条件：count < 0 说明，当前树的路径构成的字符串，与 arr 有着 1 个以上的不同字符，不可以匹配
            return false;
        }
        if (index == arr.length) {
            // 结束条件：当前 node 节点是一个字符串的结束条件，且 count 为 0（即路径上，有一个不同的字符）
            return node.isWord && count == 0;
        }
        // 遍历字典树的每个节点
        for (Character c : node.childs.keySet()) {
            // 是相同字符，count 不变；不同字符，尝试修改该字符，即将 count - 1
            int n = (c == arr[index]) ? count : count - 1;
            if (dfs(arr, node.childs.get(c), index + 1, n)) {
                // 可以匹配
                return true;
            }
        }
        return false;
    }

    /**
     * 对字符串数组 dictionary 构建字典树
     */
    public void buildTrie(String[] dictionary) {
        for (String word : dictionary) {
            Trie_767 curNode = root;
            char[] arr = word.toCharArray();
            for (char c : arr) {
                if (!curNode.childs.containsKey(c)) {
                    // 不存在该节点时，添加节点
                    curNode.childs.put(c, new Trie_767());
                }
                curNode = curNode.childs.get(c);
            }
            // 标记该节点是一个字符串的结束节点
            curNode.isWord = true;
        }
    }
}

/**
 * 解法一：哈希表（30ms）
 */
class MagicDictionary2 {
    // 键：长度，值：长度等于键值的字符串列表
    Map<Integer, List<String>> map = null;
    public MagicDictionary2() {
        map = new HashMap<>();
    }

    public void buildDict(String[] dictionary) {
        for (String dict : dictionary) {
            int len = dict.length();
            if (!map.containsKey(len)) {
                map.put(len, new ArrayList<>());
            }
            map.get(len).add(dict);
        }
    }

    public boolean search(String searchWord) {
        if (!map.containsKey(searchWord.length())) {
            // 字典中没有相同长度的字符串
            return false;
        }
        List<String> list = map.get(searchWord.length());
        for (String str : list) {
            if (oneCharDiff(str, searchWord)) {
                // 字典中存在与 searchWord 仅有一个不同字符的字符串
                return true;
            }
        }
        return false;
    }

    /**
     * 判断两个字符串是否仅有一个不同的字符
     */
    public static boolean oneCharDiff(String str1, String str2) {
        int count = 0;
        int len = str1.length();
        for (int i = 0; i < len; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                count ++;
                if (count > 1) {
                    return false;
                }
            }
        }
        return count == 1;
    }
}
